package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 12/16/20 2:27 PM
 */
public class Mirrors {

    public static void preordeTraversal(TreeNode root) {

        if (root == null) {

            return;
        }

        TreeNode node = root,preNode = null;

        while (node != null) {

            if (node.left != null) {

                preNode = node.left;

                while (preNode.right != null && preNode.right != node) {

                    preNode = preNode.right;
                }

                if (preNode.right == null) {

                    preNode.right = node;
                    System.out.println(node.val);
                    node = node.left;
                }else {

                    preNode.right = null;
                    node = node.right;
                }

            }else {

                System.out.println(node.val);
                node = node.right;
            }


        }
    }

    public static void postorderTraversal(TreeNode root) {


        if (root == null) {

            return;
        }

        TreeNode dump = new TreeNode(0);
        dump.left = root;

        TreeNode node = dump;

        while (node != null) {

            if (node.left != null) {

                TreeNode preNode = node.left;

                while (preNode.right != null && preNode.right != node) {

                    preNode = preNode.right;
                }

                if (preNode.right == null) {

                    preNode.right = node;
                    node = node.left;
                }else {


                    // 倒序输出 从 node.left 到 preNode节点之间到值
                    // 从 preNode 到 node.left
                    if (preNode == node.left) {

                        System.out.println(preNode.val);
                    }else {
                        printTreeNode(node.left,preNode);
                    }

                    node = node.right;
                    preNode.right = null;
                }

            }else {

                node = node.right;
            }

        }

    }

    private static void printTreeNode(TreeNode from, TreeNode to) {


        reversal(from,to);

        TreeNode node = to;
        while (true) {

            System.out.println(node.val);
            if (node == from) {

              break;
            }

            node = node.right;
        }

        reversal(to,from);
    }

    private static void reversal(TreeNode from, TreeNode to){

        TreeNode node = from;
        while (node != to) {

            TreeNode tmp = node.right;
            node.right.right = node;
            node = tmp;
        }

    }

}
